'''
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
有依赖的背包问题
'''
import sys
from functools import cache

money, n = map(int, input().split())
# 价格、重要度、主件编号(从1开始)
C, P = [0] * n, [0] * n
follows = [[] for _ in range(n)]
master = [False] * n
i = 0
for line in sys.stdin:
    if line == '\n': break    # for debug
    cost, weight, parent = map(int, line.split())  # 价格，权重，父组件id
    parent -= 1
    C[i] = cost
    P[i] = cost * weight
    if parent == -1:
        master[i] = True
    else:
        follows[parent].append(i)
    i += 1

# @cache
# def f(i, rest_money):
#     if i == n:
#         return 0
#     if not master[i]:  # 附件，不在这里考虑。去主件那里考虑
#         return f(i + 1, rest_money)
#     # 0) 啥都不要 1)只要自己, 2)要自己&要第一个附件 3)要自己&要第二个附件 4)要自己&要第一个附件&第二个附件
#     r0 = f(i + 1, rest_money)
#     r1 = r2 = r3 = r4 = 0
#     id1 = follows[i][0] if len(follows[i]) > 0 else -1
#     id2 = follows[i][1] if len(follows[i]) > 1 else -1
#
#     if rest_money - C[i] >= 0:
#         r1 = f(i + 1, rest_money - C[i]) + P[i]
#     if id1 != -1 and rest_money - C[i] - C[id1] >= 0:
#         r2 = f(i + 1, rest_money - C[i] - C[id1]) + P[i] + P[id1]
#     if id2 != -1 and rest_money - C[i] - C[id2] >= 0:
#         r3 = f(i + 1, rest_money - C[i] - C[id2]) + P[i] + P[id2]
#     if id1 != -1 and id2 != -1 and rest_money - C[i] - C[id1] - C[id2] >= 0:
#         r4 = f(i + 1, rest_money - C[i] - C[id1] - C[id2]) + P[i] + P[id1] + P[id2]
#     return max(r0, r1, r2, r3, r4)
# print(f(0, money))

# def f2():
#     dp = [[0] * (money + 1) for _ in range(n + 1)]
#     # 第一维度依赖后边的，第二维度依赖前边的
#     for i in range(n - 1, -1, -1):
#         if not master[i]:
#             dp[i][:] = dp[i + 1][:]
#             continue
#         for rest_money in range(money + 1):
#             r0 =dp[i + 1][rest_money]
#             r1 = r2 = r3 = r4 = 0
#             id1 = follows[i][0] if len(follows[i]) > 0 else -1
#             id2 = follows[i][1] if len(follows[i]) > 1 else -1
#
#             if rest_money - C[i] >= 0:
#                 r1 = dp[i + 1][rest_money - C[i]] + P[i]
#             if id1 != -1 and rest_money - C[i] - C[id1] >= 0:
#                 r2 = dp[i + 1][rest_money - C[i] - C[id1]]+ P[i] + P[id1]
#             if id2 != -1 and rest_money - C[i] - C[id2] >= 0:
#                 r3 = dp[i + 1][rest_money - C[i] - C[id2]] + P[i] + P[id2]
#             if id1 != -1 and id2 != -1 and rest_money - C[i] - C[id1] - C[id2] >= 0:
#                 r4 = dp[i + 1][rest_money - C[i] - C[id1] - C[id2]] + P[i] + P[id1] + P[id2]
#             dp[i][rest_money] = max(r0, r1, r2, r3, r4)
#     return dp[0][-1]
# print(f2())


def f3():
    A = [0] * (money + 1)
    # 第一维度依赖后边的，第二维度依赖前边的
    for i in range(n - 1, -1, -1):
        if not master[i]:
            continue
        B = [0] * (money + 1)
        for rest_money in range(money + 1):
            r0 = A[rest_money]
            r1 = r2 = r3 = r4 = 0
            id1 = follows[i][0] if len(follows[i]) > 0 else -1
            id2 = follows[i][1] if len(follows[i]) > 1 else -1

            if rest_money - C[i] >= 0:
                r1 = A[rest_money - C[i]] + P[i]
            if id1 != -1 and rest_money - C[i] - C[id1] >= 0:
                r2 = A[rest_money - C[i] - C[id1]]+ P[i] + P[id1]
            if id2 != -1 and rest_money - C[i] - C[id2] >= 0:
                r3 = A[rest_money - C[i] - C[id2]] + P[i] + P[id2]
            if id1 != -1 and id2 != -1 and rest_money - C[i] - C[id1] - C[id2] >= 0:
                r4 = A[rest_money - C[i] - C[id1] - C[id2]] + P[i] + P[id1] + P[id2]
            B[rest_money] = max(r0, r1, r2, r3, r4)
        A = B
    return A[-1]
print(f3())
